package assign1;
/* COMP 3760 - Algorithm Analysis and Design
 * Assignment #1 - Mnemonic Monkey
 * Stacy Mitchell	A00816991
 * Vukasin Simic	A00801474
 * 
 * October 14, 2012
 * 
 * Subsets.java
 * 
 * Abstract class containing the getSubsets() function used to generate all possible (2^n) subsets of a set containing all values from 1 to n.
 * 
 * The code is based on the blog entry available at: http://compprog.wordpress.com/2007/10/10/generating-subsets/
 * 
 */
import java.util.ArrayList;
import java.util.List;
import java.util.Map;

abstract public class Subsets {
	
	//NOTE: this function is not used by Mnemonic, a derived version named getSubsets() found below is used.
	/*Java Equivalent of the following C code:
	//Applies the mask to a set like {1, 2, ..., n} and prints it 
	int main(int argc, char *argv[]) {
		int n = 3;
		 
    	int mask[16];
	    int i;
	    for (i = 0; i &lt; n; ++i)
	        mask[i] = 0;
	 
	    printv(mask, n);
	 
	    while (next(mask, n))
	        printv(mask, n);
	 
		return 0;
	}*/
	public static void main(String[] args) {
		int n = 3;
		
		boolean[] mask = new boolean[n]; //values initialized to false by default
		
		printMask(mask, n);
		
		while(nextMask(mask, n)){
			printMask(mask, n);
		}
	}
	
	//NOTE: this function is not used by Mnemonic, a derived version named getSubset() found below is used.
	/* Java Equivalent of:
	void printv(int mask[], int n) {
	    int i;
	    printf("{ ");
	    for (i = 0; i &lt; n; ++i)
	        if (mask[i])
	            printf("%d ", i + 1);
	    printf("\\b }\\n");
	}*/
	private static void printMask(boolean[] mask, int n){
		int i;
		System.out.print("{ ");
		for (i = 0; i < n; i++){
			if (mask[i]){
				System.out.printf("%d ", (i + 1));
			}
		}
		System.out.println("\b }");
	}
	
	//This function is used by getSubsets() to generate the next subset.
	/* Java Equivalent of:
	int next(int mask[], int n) {
	    int i;
	    for (i = 0; (i &lt; n) &amp;&amp; mask[i]; ++i)
	        mask[i] = 0;
	 
	    if (i &lt; n) {
	        mask[i] = 1;
	        return 1;
	    }
	    return 0;
	}*/
	private static boolean nextMask(boolean[] mask, int n){
		int i;
		for (i = 0; (i < n) && mask[i]; i++){
			mask[i] = false;
		}
		if (i < n){
			mask[i] = true;
			return true;
		}
		return false;
	}
	
	//Derived from printMask(), instead of printing the generated set to StdOut, returns it.
	private static List<Integer> getSubset(boolean[] mask, int n){
		List<Integer> set = new ArrayList<Integer>();
		for (int i = 0; i < n; i++){
			if (mask[i]){
				set.add(i + 1);
			}
		}
		return set;
	}
	
	/* Derived from main(), uses nextMask() and getSubset() to generate all possible (2^n) subsets of a set containing all values from 1 to n.
	 * Changes made include: adding a program runtime timeout check, returning generated subsets rather than just printing them and not saving to memory subsets
	 * that contain labs with no MemoryRequired or sets containing more MemoryRequired than the CHIP_MEMORY_AVAILABLE memory limit.
	 */
	public static List<Subset> getSubsets(int n, boolean[] noMemLabs, List<Map<String,Integer>> lab_list, int max_memory, long programStartTime, long caseStartTime){
		List<Subset> subsets = new ArrayList<Subset>();
		boolean[] mask = new boolean[n]; //values initialized to false by default
		List<Integer> temp_list;
		int total_memory = 0;
		boolean containsZero = false;
		
		while(nextMask(mask, n)){
			total_memory = 0;
			temp_list = getSubset(mask, n);
			
			for (int i = 0; i< noMemLabs.length; i++){
				if(noMemLabs[i] && temp_list.contains(i)){
					containsZero = true;
				}
			}
			if (!containsZero){
				for (int lab_num : temp_list){
					total_memory += lab_list.get(lab_num).get("memory_required");
				}
				if (total_memory <= max_memory){
					subsets.add(new Subset(temp_list, total_memory));
				}
			}
			Mnemonic.checkTimeout(programStartTime,caseStartTime);
		}
		return subsets;
	}
}
